// m

// 给定一个无重复元素的正整数数组candidates和一个正整数target，找出candidates中所有可以使数字和为目标target的组合
// 数组candidates中的数字在每个组合中只能使用一次，1 <= candidates <= 50

// 解题思路，和上一题不同之处在于不能有重复组合，所以关键步骤在于去重
// 在回溯遍历的时候，下一层递归的start_index要从当前节点的后一位开始遍历，即i+1开始，
// 而且统一递归层不能用相同的元素

function combinationSum2(candidates, target) {
    let res = []
    let path = []
    function backtrack(candidates, target, sum, start_index) {
        if (sum > target) {
            return
        }
        if (sum === target) {
            res.push([...path])
            return
        }
        for (let i = start_index; i < candidates.length; i++) {
            if (sum + candidates[i] > target) {
                break
            }
            if (i > start_index && candidates[i] === candidates[i - 1]) {
                continue
            }
            sum += candidates[i]
            path.push(candidates[i])
            backtrack(candidates, target, sum, i + 1)
            sum -= candidates[i]
            path.pop()

        }
    }
    candidates.sort((x, y) => x - y)
    backtrack(candidates, target, 0, 0)
    return res
}

let candidates = [10, 1, 2, 7, 6, 1, 5], target = 8
console.log(combinationSum2(candidates, target))